#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
}; 

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        return merge(list1, list2);
    }

    ListNode* merge(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        if (list1->val < list2->val) {
            list1->next = merge(list1->next, list2);
            return list1;
        }
        else {
            list2->next = merge(list1, list2->next);
            return list2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution01 {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return nullptr;
        if (head->next == nullptr) return head;
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ret;
    }

};


class Solution02 {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* ret = swapPairs(head->next->next);
        ListNode* next = head->next;
        next->next = head;
        head->next = ret;
        return next;
    }
};

class Solutionxx {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        bool flag = true;
        if (n < 0) flag = false;
        long long nx = (long long)abs(n);
        double ret = 1;
        if (nx % 2 == 1)
            ret *= x;
        double tmp = myPow(x, nx / 2);
        ret *= tmp * tmp;
        if (flag == false)
            ret = 1 / ret;
        return ret;
    }
};